4892. Замена

Дана последовательность натуральных чисел из n элементов. Требуется каждый элемент заменить на ближайший следующий за ним (то есть с большим индексом) элемент, который строго больше его по значению. Если большего элемента после данного нет, следует заменить данный элемент на ноль.

Вход. Первая строка содержит число элементов n (1 ≤ n ≤ 10⁵). Вторая строка содержит n натуральных чисел a_i (a_i ≤ 10⁹) – значения элементов последовательности.

Выход. Выведите искомую последовательность, разделяя соседние элементы одним пробелом.

Пример входа 1	Пример выхода 1
6 1 2 3 1 1 5	2 3 5 5 5 0
Пример входа 2	Пример выхода 2
5 1 2 3 4 5	2 3 4 5 0

РЕШЕНИЕ

структуры данных - set

Анализ алгоритма

Пусть числа входной последовательности a₁, a₂, …, a_n соответствуют высотам домов, расположенных рядом друг с другом. Например, первый тест можно изобразить следующим образом:

Пусть b₁, b₂, …, b_n – результирующий массив. Тогда b_i равно такому a_j, что если посмотреть в торец i-го дома слева, то дом a_j будет ближайшим видимым. Очевидно, что b_n = 0.

Будем обрабатывать дома справа налево. Пусть a_i – текущий рассматриваемый дом. Будем поддерживать множество s высот домов, видимых с левого торца i-го дома (включая a_i). Тогда b_i равно второму элементу множества s.

Рассмотрим, как поддерживать множество s при добавлении нового дома. Двигаемся справа налево, пусть уже был рассмотрен третий дом с высотой a₃ = 1. Текущее множество равно s = {1, 2, 3, 5}. Обрабатываем второй дом с высотой a₂ = 4. Очевидно, что он перекроет вид слева на все дома, не больше его высоты. Следует добавить значение a₂ = 4 во множество s, после чего удалить из s все числа, меньшие a₂ = 4 (можно воспользоваться методом erase для промежутка). После описанных операций множество примет вид s = {4, 5}.

Реализация алгоритма

Объявим множество s и итератор it на него. Входную и выходную последовательности храним в массивах in и out.

#define MAX 100001

set<int> s;

set<int>::iterator it;

int in[MAX], out[MAX];

Читаем входной массив.

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d",&in[i]);

Обрабатываем дома справа налево.

for(i = n - 1; i >= 0; i--)

{

Вставляем во множество высоту текущего дома.

s.insert(in[i]);

Ищем позицию высоты in_i вставленного дома. Удаляем из множества s все высоты, меньшие in_i.

it = s.find(in[i]);

s.erase(s.begin(),it);

Выводим второй элемент множества. Если его не существует, выводим 0.

it++;

if(it == s.end())

out[i] = 0;

else

out[i] = *it;

}

Выводим результирующий массив.

for(i = 0; i < n; i++)

printf("%d ",out[i]);

printf("\n");